\input{description_intro}

\MySection{Primitives}\label{SFTerminal}
\input{primitives}

\MySection{\GT}
\input{goaltype}

\MySection{Alleles and Gene Pool}
%MODIFICATION_A 1 gene pool for the whole ecosystem
\noindent
An {\em allele} is a structure that aggregates a normalized \SF{} term with some other information.
Alleles are stored in the ecosystem's {\em gene pool} where they are ordered by the type of the term they enclose. \emph{There is one and only one gene pool for the whole ecosystem}. An allele includes an \field{id} field, unique among the other alleles of the same type in the gene pool.
An allele also includes a selection probability, stored in its \field{selectionProb} field. New alleles are generated
by mutating existing alleles, either:
\begin{enumerate}
\item as part of a random gene creation cycle, in which an allele is selected for mutation as a {\em seed} by roulette wheel selection in proportion to its \field{selectionProb} value.
\item as a by-product of a crossover operation between two genotypes (see \ref{xoverGeneral})
\end{enumerate}
\noindent
An allele's \field{useInEcosystem} field counts the number of genotypes by which it is carried and its \field{geneFitness} field records the average fitness of the genotypes that carry it. Together, these two values are the main factors used  to compute \field{selectionProb} in the general case. The only exception to this is in the creation of the first generation, as the gene pool is created before the genotypes of the ecosystem. In general, \field{selectionProb} relates to the usefulness of the allele as a building block in the ecosystem. The formal definition of an allele is given below:
\begin{definition}[$<\mathit{Allele}>$]\label{genedef}
\begin{verbatim}

<Allele> ::= {
        expression : <Term>;
        id : <Int>;
        selectionProb : <Float>;
        useInEcosystem : <Int>;
        geneFitness : <Float>;
    }
\end{verbatim}
\end{definition}

\subsection{Allele Complexity}\label{gencomp102}
\noindent
The random process by which alleles are produced implies that some new alleles may be quite large. There is a parsimony measure which is used to limit the size of an allele. It corresponds to the {\em complexity} of the term it expresses. This measure is arbitrary, but its purpose is to provide a sense of the size of the term that an allele contains. This allows an ABGP system to reject alleles that it considers too large.
\begin{samepage}
    \begin{definition}[Expression Complexity]
    \noindent
    The complexity of an expression is defined as:

    \begin{enumerate}
    \item Type constants and type variables have complexity 1.
    \item Arrow types have the complexity of their left type plus the complexity of their right type, plus 1.
    \item The complexity of an abstract type is the complexity of the body of its abstraction plus 1.
    \item The complexity of a term constant or variable is 1.
    \item The complexity of an application term is the sum of the complexities of its two arguments plus 1.
    \item The complexity of an abstract term is the complexity of the body of the abstraction plus 1.
    \item The complexity of a term abstracted by type is the complexity of the body of the abstraction plus 1.
    \item The complexity of a term/type application (such as $((\Lambda X. \la {x}{X}.x)\ \typ{Int})$) is the sum of the complexities of the term on the left side and of the type on the right side.
    \end{enumerate}

    \end{definition}
\end{samepage}
\noindent
In the implementation, the complexity of an expression is
computed by the function $\mathit{complexity\_of\_expr}$.
\maxGeneComp\index{\maxGeneComp} is the value that specifies an
upper-bound on the size of the alleles that may be included in the
gene pool of an ABGP system. It is provided to the system at the
time of the system's initialization by the system's designer. When
new alleles are created, they may only be included in the gene pool
if their size is smaller than $\maxGeneComp$. As it turns out, one
of the results that was obtained during the course of this research
is that this value is crucial to the performance of an ABGP run (see
\ref{maxgenecompimotance}).

\subsection{Gene Pool}
\noindent
As mentioned previously, alleles are stored in a {\em gene pool}, which is a wrapper for a hash table in which the keys are types and the values are lists of alleles that contain expressions of the same type as the key index that indexes the lists. Only one copy of an allele may exist in the gene pool at any one time. The definition of a gene pool is below:
\begin{definition}[Gene Pool]\label{gpDefinitionMain}

\begin{verbatim}

   <GenePool> := (<Type>, <Allele> list) Hashtbl

\end{verbatim}
\end{definition}
\subsection{The Gene Pool's Kernel}
Given a context $C$ and a \GT, the kernel of the gene pool is constructed thus:
\begin{enumerate}
    \item The typed free variables and the names for \SF{} terms in $C$ are entered in the gene pool as new alleles, with their
    types as corresponding genes.
    \item A series of constructors for the type \GT{} are produced and entered in the gene pool. The constructors are produced using
    the $make\_constructors$ function. The constructors are automatically deduced from \GT{} using the $make\_constructors$ function. They are included in the original gene pool as functions guaranteed to result in the production of an object of type \GT. The inclusion of such functions facilitates the discovery process of new species.
    \end{enumerate}
We do not include the pseudo-code for the $make\_constructors$
function as it is a rather complex function that uses context
shifting and translation operations on types which are of little
interest in the present discourse (the actual OCaml implementation
code is given in appendix \ref{importantFunction}). However, as it
is a central function of the system, we will describe what it does.
The function takes a type $\typ{C}$ that has the form
$\typ{\AT{A}{B}}$ in which $\typ{A}$ is a data type (in the required
format) and outputs a series of functions that may be used to
construct objects of type $\typ{C}$. The functions are created using
a fresh bound variable $x$ of type $\typ{A}$ and applying $(x\
\typ{B})$ to successive new bound variables to yield an object of
type $\typ{B}$. This object is then used as the inner body of a
series of functional abstractions built using the possible
permutations of the variables created during the process. For
example, when given the following type as input:
\begin{equation*}
\typ{\AT{TyBool}{Int}}
\end{equation*}
the function outputs the following constructors:
\begin{align*}
\la{x}{Int}.\la{y}{Int}.\la{a}{TyBool}.a\ [Int]\ x\ y\\
\la{y}{Int}.\la{x}{Int}.\la{a}{TyBool}.a\ [Int]\ x\ y
\end{align*}
Output \ref{outMakeCons1} and \ref{outMakeCons2} provide two more examples of the function's behavior,
 obtained using the context \ref{ListStr}:

\begin{output}[h]
{\small
\begin{verbatim}
The type: [(TT T. T-> (TyBool-> T)-> (Int-> T)-> T)-> Int] is
constructible by the following 6 terms:

    1. lam m:TyBool-> Int.lam q:Int.lam r:Int-> Int.
    lam q':TT G. G-> (TyBool-> G)-> (Int-> G)-> G.q' [Int] q m r

    2. lam d:TyBool-> Int.lam i:Int-> Int.lam b:Int.
    lam b':TT S. S-> (TyBool-> S)-> (Int-> S)-> S.b' [Int] b d i

    3. lam m:Int-> Int.lam d:TyBool-> Int.lam i:Int.
    lam k:TT N. N-> (TyBool-> N)-> (Int-> N)-> N.k [Int] i d m

    4. lam j:Int-> Int.lam u:Int.
    lam y:TyBool-> Int.
    lam o:TT S. S-> (TyBool-> S)-> (Int-> S)-> S.o [Int] u y j

    5. lam c:Int.lam g:Int-> Int.lam r:TyBool-> Int.
    lam y:TT G. G-> (TyBool-> G)-> (Int-> G)-> G.y [Int] c r g

    6. lam r:Int.lam b:TyBool-> Int.lam n:Int-> Int.
    lam l:TT R. R-> (TyBool-> R)-> (Int-> R)-> R.l [Int] r b n
\end{verbatim}}
\caption{}\label{outMakeCons1}
\end{output}

\begin{output}[h]
{\small
\begin{verbatim}
The type: [TyList-> Int-> String] is constructible by the following
2 terms:

    1.lam c:String-> (Int-> String)-> Int-> String.
    lam i:Int-> String.lam a:TyList.a [Int-> String] i c

    2. lam m:Int-> String.
    lam t:String-> (Int-> String)-> Int-> String.
    lam x:TyList.x [Int-> String] m t
\end{verbatim}}
\caption{}\label{outMakeCons2}
\end{output}

\subsection{Gene Diversity}\label{genediversity}
%MODIFICATION_A 1 diversity clarifications
Using the OCaml built-in $hash$ function in conjunction with the nameless representation style,
it is relatively easy to compare terms by structure. What we compare in this case are alleles, not genes. We only need to compare alleles if
they have the same type (alleles of the same gene). The function $hash$ takes a parameter $depth$ up to which it compares structures.
If two structures are similar (up to $depth$), the function returns the same value for both. We applied
this to expressions as a method to differentiate alleles from each other. Each allele's expression-dependent
hash value is computed, and alleles that are too similar to existing alleles are refused entry into the gene pool.
We decided to use this feature as we realized that the diversity of the genes contained in the gene pool had an impact on the performance of
the system. As a result, we incorporated a global user input parameter \geneDiff{} into the design of the system. The value \geneDiff{} is used as a parameter to the OCaml $hash$ function which is then used to compare new genes to existing genes in the gene pool. When this value
is higher, a gene needs to be ``more different" than the other genes in the gene pool in order to be included in the gene pool. The impact of
this parameter is discussed in section \ref{diversGene}. The down-side of using this method to encourage genetic diversity is that the
cost of the computation of the hash value for each allele is high and that the higher the precision to which it is set, the more new genes
need to be produced to fill up the gene pool as more genes are refused entry.

\subsection{Generating New Gene Pools}\label{hjdsh784}
\noindent
Each new generation's gene pool, including the first generation,
is constructed by mutating alleles that are already in the
gene pool to produce new alleles. The system-wide variable \maxComp{}
defines a ceiling on the sum of the complexity of the alleles that
are in the gene pool at any one time. The terms defined in the
system's terminal set (as defined by the GP's context) and the constructors derived
from \GT{} are used to build the kernel of the first gene pool which is then constructed
to \maxComp{} as any other gene pool would be. Each allele is assigned a probability of
being selected as a seed.
The probability of being selected as a seed is set for each element of the gene pool's kernel as:
\begin{equation}
\frac{1}{n}
\end{equation}
where $n$ is the initial number of allele obtained by the direct translation of the expressions in the GP's context and of the \GT{} constructors into alleles. For the next generations, the probabilities are calculated as functions of the fitness of the genotypes that carry the alleles. The probability is stored in the \field{selectionProb} field of each allele. Each allele is chosen as a seed with probability \field{selectionProb} and a set of descendent alleles is thus produced. Before insertion, the probability $p$ of the seed allele is divided by $d + 1$, were $d$ is the cardinality of the set of its descendent alleles, to yield its new selection probability, as well as the selection probability of each of its descendants. This scheme is designed to encourage diversity optimization.  For example, given the context of table \ref{BooleanTerminals}, the initial set of alleles is created as:
\begin{verbatim}
type: TyBool
 id:1 - exp:true - selectionProb:0.5
 id:0 - exp:false - selectionProb:0.5
\end{verbatim}
Giving each of the two original alleles of the  $\typ{TyBool}$ gene an equal chance of being chosen as seeds. Following the initial construction of the gene pool, if 4 new alleles are constructed by mutating the allele that expresses $true$, the new selection probabilities will be set as:
{\small
\begin{verbatim}
type: TT D. (D-> D-> D)-> D-> D-> D
 id:0 - exp:Lam V.lam k:V-> V-> V.lam a:V.k a - selectionProb:0.1
type: TT Q. (Q-> Q)-> (TyBool)-> Q-> Q
 id:0 - exp:Lam M.lam d:M-> M.lam e:TyBool.lam u:M.e [M] (d u) u - selectionProb:0.1
type: TT M. (TT H. H-> (M-> H-> H)-> H)-> M-> (M-> M-> M)-> M
 id:0 - expression:Lam T.lam w:TT W. W-> (T-> W-> W)-> W.w [T] - selectionProb:0.1
type: TT L. L-> L
 id:0 - exp:Lam T.lam a:T.a - selectionProb:0.1
type: TyBool
 id:1 - exp:true - selectionProb:0.1
 id:0 - exp:false - selectionProb:0.5
\end{verbatim}}
\noindent
As there are now 5 alleles sharing the initial selection probability $0.5$ of the allele that expresses $true$. In this example, when the next round of gene creation occurs, the allele expressing $false$ is 5 times more likely than any other allele in the gene pool to be chosen as the next seed. Appendix \ref{genepoolex1} lists the elements of a gene pool randomly generated from the primitives defined in table \ref{tab:ctxex1}.



\subsection{Generating New Alleles}
\noindent
When a new set of alleles is created by seed mutation, the alleles from the descendant set that are not already in the gene pool and that do not violate size constraints (see section \ref{gencomp102}) are added to the gene pool. There are many possible mutation operations that may be applied to a seed to generate a set of descendant genes. For example:
\begin{enumerate}
\item If the seed is an allele whose \field{expression} field contains the term $t$, of type $\typ{\Pi X.V}$, then one can generate the descendant set of all alleles with expression $(t\ A)$, where $A$ is a type that exists in the gene pool. The $geneId$ field for each of these new alleles is assigned by the system, and we describe the process by which a value is assigned to the $selectionProb$ field in  \ref{hjdsh784}.

\item If the seed has its \field{expression} field $t$, of type $\typ{\AT{A}{B}}$, then one can generate the descendant set of alleles with expression $(t\ a)$, where $a$ is a gene expression of type $A$ that exists in the gene pool.

\item If the seed has its \field{expression} field $t$, of type $\typ{T}$, that contains a constant $a^A$, then one can generate the descendant set (of one element) of alleles with expression  $(\la{x}{A}.\repl{t}{x}{a})\text{ of type $\typ{\AT{A}{T}}$}$

\item If the seed has its \field{expression} field $t$, of type $\typ{T}$ that contains a type constant $\typ{A}$, but does not contain any term constant of  type $\typ{A}$ then one can generate the descendant set (of one element) of alleles with expression  $(\Lambda X . \repl{t}{X}{A})\text{ of type $\typ{\Pi X. \repl{T}{X}{A}}$}$
\end{enumerate}
There are many other possibilities. The set of rules that we use in this research was obtained by trial and error. We list these mutation rules in appendix \ref{mutgenerules}, but they include the four listed above.


\MySection{Species}\label{SpeciesDes}
\input{speciesDes}


\MySection{Genotypes}\label{GenotypeSection}
%section 6.6 (page 98)
\noindent
{\em Genotypes} are arrangements of alleles. The arrangement is specified by the species to which a genotype belongs.
A genotype in ABGP is basically a tree in which the leaves may be either the id of alleles that exist in the gene pool
or types.
\begin{definition}[Genotype Definition (ABGPS)]\label{GTDef4}
\begin{verbatim}

<genotype> ::=  | "AlleleId" <int>
                | "TA" <genotype> <ty>
                | "FA" <genotype> <genotype>

\end{verbatim}
\end{definition}

\begin{figure}[h]
\centering \epsfig{file=speciestogenotype1.eps, width=150mm}
\caption{Four genotypes that belong to the same species and the subset of the gene pool that contains the alleles that compose them}
\label{threegenotypesandspecies}
\end{figure}
\noindent It is clear from the definition that a genotype on its own
doesn't do much. A genotype can only be interpreted as a computer
program in the wider context of the gene pool with which it is
associated and of the species to which it belongs. Knowing which
species a genotype belongs to and having the gene pool to which it
relates is the only way to know which alleles are referred to by the
``AlleleId" part of the genotype. As a consequence, whenever a
function is called that uses a genotype as its argument, that
function will usually also have a gene pool and a species as
complementary arguments. Figure \ref{threegenotypesandspecies}
represents four genotypes that belong to the species defined in
section \ref{SpeciesDes}. Given a species $spec$ and a gene pool
$genes$, the function $genotypeNum$ (listing \ref{genotypeNum})
returns the number of different possible genotypes that may be
constructed. Within $genotypeNum$, the functions $tyMem$ and
$tyFind$ on $genes$ are used. The $tyMem$ function takes a type and
a gene pool as arguments and answers true if the type is a gene in
the gene pool, while $tyFind$ takes a gene (which is a type) and a
gene pool as argument and returns the list of alleles associated
with the gene.
\begin{Program}[h]
\begin{verbatim}
genotypeNum genes spec =
\end{verbatim}
\begin{comment}
The $tnum$ sub-routine, below, returns the number of alleles
of a gene $\typ{Ty}$
\end{comment}
\begin{verbatim}
    let tnum [Ty] =
        match tyMem genes [Ty] with
        |true --> List.length (tyFind genes [Ty])
        |false --> 0 in

    match spec with
    | Partial _ --> 0
    | Gene [Ty] --> tnum [Ty]
    | TTelim sub_spec _ --> genotypeNum genes sub_spec
    | ->Elim sub_spec1 sub_spec2 -->
        (genotypeNum sub_spec1) * (genotypeNum sub_spec2)
\end{verbatim}
\caption{The $genotypeNum$ function}\label{genotypeNum}
\end{Program}
Moreover, given a species $spec$ and a gene pool $genes$, a simple
modification to the $genotypeNum$ function yields the
$all\_genotypes$ function which creates all the possible genotypes
that belong to $spec$.  As genotypes are often created in such
groups, they are differentiated in status within the system by being
associated with a $\mathit{genoStatus}$ object. Objects of type
$\mathit{genoStatus}$ are defined as:
\begin{verbatim}

<genoStatus> ::=  | "Dead" <float>
                  | "Alive" <float>
                  | "Unborn"
\end{verbatim}
This corresponds to the three possible state in which a genotype may
exist:
\begin{itemize}
\item An unborn genotype is a genotype that hasn't been evaluated yet.
\item A genotype is marked as `Dead' to indicate that it has
been evaluated, but has no more role to play in the production of
new generations and will never again be selected for crossover.
\item A genotype marked as `Alive' may be used as a selection tool during the
construction of the next generation. At the beginning of each
generation (except the initial one), there are
\populationDefaultSize{}\index{\populationDefaultSize} genotypes
marked as `Alive' in the system. \populationDefaultSize{} is the
input parameter that defines the size of the ecosystem in terms of
programs to evaluate during the current generation.
\end{itemize}

\subsection{Populations}
%MODIFICATION_A clarification on population and populationDefaultSize parameter
\noindent
The associations between genotypes and their status is
recorded within a $Population$ object. Each species (proof) is associated with a unique $Population$
structure and an ecosystem encasulates several $Population$ structures. The total number of individuals marked as `Alive' in the
whole ecosystem is defined by the parameter \populationDefaultSize. An object of type $Population$ is defined as:

\begin{verbatim}

<Population> ::= {
     pattern : <Species>;
     fitness : <float>;
     genotypes : (<genotype>, <genoStatus>) Hashtbl;
     }
\end{verbatim}
We also make use of the function: $\mathit{alive\_population}\ :\
\AT{Population}{\mathbb{N}}$ to obtain the number of genotypes
marked as `Alive' in a population.


\subsection{Generating New Genotypes}\label{GenoSpawn}
Given a species $spec$ and a gene pool $genes$, we may create $n$
genotypes, provided that: \begin{equation*} (genotypeNum\ genes\
spec) - (\mathit{alive\_population}\ pop) \geq n
\end{equation*}
\noindent holds, where $pop$ is the population associated with
$spec$. The function:
\begin{equation*}
birth\_genotypes\_of\_species\ genes\ spec\ n
\end{equation*}
results in $n$ new genotypes of the species $spec$ being marked as
`Alive'. These genotypes may be found in the set of previously
created genotypes marked as `Unborn' or may be created outright.
The\\ $birth\_genotypes\_of\_species$ function implements an effort
to maximize the genetic diversity of the population associated with
$spec$. This is done by assigning a temporary counter to each allele
in $genes$ that are or may be used to construct organisms of the
species $spec$. The counters are incremented as new live genotypes
are added to the population. The idea is to make each allele's
probability of being selected to be part of a new live genotype
inversely proportional to the number of times it has already been
chosen for that purpose. To do this, the system selects the alleles
with their counter set at the lowest possible as genes for each new
genotypes marked as `Alive'. In the example below, initial counters
are presented for each allele in the gene pool of figure
\ref{threegenotypesandspecies}. For example, at the very beginning
of the spawning process, when no genotype is alive, the counters for
each allele are set to 0: {\small
\begin{verbatim}
|Gene Pool Dump 1           |
[TT X.X->(Object->X)->X]
    id:0 : 0
    id:1 : 0
    id:2 : 0
[Behavior]
    id:0 : 0
    id:1 : 0
    id:2 : 0
[Object->Behavior]
    id:0 : 0
    id:1 : 0
\end{verbatim}}
\noindent after the following genotype is switched from `Unborn' to
`Alive' and is inserted in the population:
\begin{verbatim}
<FA
    <FA
        <TA <AlleleId 2><[Behavior]>>
        <AlleleId 1>>
    <AlleleId 1>>
\end{verbatim}
the counters are set at:
{\small
\begin{verbatim}
|Gene Pool Dump 2           |
[TT X.X->(Object->X)->X]
    id:0 : 0
    id:1 : 0
    id:2 : 1
[Behavior]
    id:0 : 0
    id:1 : 1
    id:2 : 0
[Object->Behavior]
    id:0 : 0
    id:1 : 1
\end{verbatim}}
\noindent There are now several possibilities for the next new
genotype. It might, for example, be:
\begin{verbatim}
<FA
    <FA
        <TA <AlleleId 1><[Behavior]>>
        <AlleleId 0>>
    <AlleleId 0>>
\end{verbatim}
which would set the counters at:
{\small
\begin{verbatim}
|Gene Pool Dump 3           |
[TT X.X->(Object->X)->X]
    id:0 : 0
    id:1 : 1
    id:2 : 1
[Behavior]
    id:0 : 1
    id:1 : 1
    id:2 : 0
[Object->Behavior]
    id:0 : 1
    id:1 : 1
\end{verbatim}}
\noindent
As a result of this sequence of operations, the next genotype would have to carry
allele 0 from the gene $\typ{\Pi X. \AT{X}{\AT{(\AT{Object}{X})}{X}}}$ and allele 2
from the gene $\typ{Behavior}$.


\newpage
\MySection{Phenotypes}\label{Phenotypes}
%MODIFICATION_A compile==>interpret
\begin{figure}[h]
\centering \epsfig{file=ABGP_Geno_Ex1.eps, width=150mm}
\caption{A non-evaluated phenotype assembled from alleles contained in a gene pool built using the context
defined in table \ref{tab:ctxex1} and the species it belongs to (right)} \label{ABGPSGenoEx1}
\end{figure}
\noindent
As per the definitions provided in 2.1, the system's interpreter  derives a phenotype from
a genotype. The $interpret$ function matches each of the leaf building  block of a genotype with the expression of the allele to which it is a pointer and normalizes the resulting expression. Figure \ref{ABGPSGenoEx1}
illustrates the STN tree form of the phenotype:
    \begin{equation}\label{ExpressionForGpexb34}
    (plus\ 2\ (plus\ 1\ (gt\ time\ 10\ \typ{Int}\ 3\ 4)))
    \end{equation}

\noindent
    The function $interpret$  (program \ref{phenoofgeno}) takes a gene pool, a species and a genotype as arguments and returns
    the phenotype associated with the genotype. The function $get\_term$ is used to extract the term expressed by an allele using the
    allele's id and its type, while $\mathit{TmTApp}$ is used to construct a type application from a term and a type
    and $\mathit{TmApp}$ is used to construct a term application from two terms. The $normalize$ function does what its name indicates.
    It is possible to obtain the same phenotype from the conversion of different genotypes, even when they belong to different species.
    Figure \ref{genotypesToSamePhenotype} illustrates this.
\begin{Program}[h]
{\small
\begin{verbatim}
interpret genes species genotype =

    let non_normalized_term =
        match (species , genotype) with
        | (Gene [ty], AlleleId id) -->  get_term genes ty id

        | (TTelim species [ty1] , TA genotype [ty2]) when ty_eqv [ty1] [ty2] -->
            TmTApp (interpret genes species genotype) [ty1]

        | ((->elim spec1 spec2) , (FA gtype1 gtype2)) -->
            TmApp (interpret genes spec1 gtype1) (interpret genes spec2 gtype2)

        | _->failwith "Invalid pair proof/program" in

    normalize non_normalized_term
\end{verbatim}}
\caption{The $interpret$ function}\label{phenoofgeno}
\end{Program}

    \begin{figure}[h]
    \centering \epsfig{file=SeveralPossibleGenotypesEvaluatingToSamePhenotype.eps, width=150mm}
    \caption{The same phenotype results from these three different genotypes as they
    normalize to the same term}\label{genotypesToSamePhenotype}
    \end{figure}





\MySection{The ABGP Ecosystem}\label{EcosystemSection}
\noindent In many ways, the ecosystem {\em is} the ABGP system. It
brings all the elements presented so far into one data structure. An
object of type {\em Ecosystem} is a tuple defined as:

\begin{samepage}
\begin{definition}[Ecosystem]
\begin{verbatim}

   Ecosystem  ::= {
        generation_count : <int>;
        context : Binding * string list
        goal_type : <ty>;
        genes : <GenePool> ;
        kingdom : (<Species>,  <Population>) Hashtbl
   }

\end{verbatim}
\end{definition}
\end{samepage}
\noindent
The attribute $kingdom$ is a hash table. The keys are
objects of type $Species$ and the values are objects of type
$Population$. We make use of the the implemented function
$\mathit{alive\_eco}\ :\ \AT{\mathit{Ecosystem}}{\mathbb{N}}$ to
obtain the number of genotypes marked as `Alive' in an ecosystem,
and of $\mathit{unborn\_eco}\ :\
\AT{\mathit{Ecosystem}}{\mathbb{N}}$ to obtain the number of
genotypes marked as `Unborn' in an ecosystem.
\subsection{Generating the Initial Ecosystem}
\begin{description}

\item[1. Init]
    \begin{enumerate}
     \item A context is provided to $eco$, it forms the basis for the gene pool $genes$.
     \item \label{readInput} The system deduces \GT{} from provided test cases
     list or it is explicitly provided by the system's user.
     \end{enumerate}

 \item[2. GrowPool] \label{init} The gene pool is grown randomly to size \maxComp{ } by randomly mutating the
     genes that are already in the gene pool.  No new gene may be larger than
     \maxGeneComp{} and larger genes are discarded. Moreover, each new allele has to be distinct from the
     alleles currently in the gene pool by the value \geneDiff{}.

 \item[3. IsReady?] The number of possible genotypes in $eco$ is computed
    based on the species in the system and the type and number of
     genes in the gene pool using the $genotypeNum$ function. If it is possible to
     produce \populationDefaultSize{} genotypes, go to $BuildGeneration$, otherwise
     go to step $AddSpecies$

 \item[4. AddSpecies] \label{speciesSpawn2}Produce one new species, either by modifying
     species already in the ecosystem or by brute search for
     new proofs of \GT{} with limited depth, using the genes
     in the gene pool as propositions. Delete all the alleles in the gene pool that
     can not be used in any of the species currently in the ecosystem. Go to step $GrowPool$.
%MODIFICATION_A clarification of eqn
 \item[5. BuildGeneration] The total potential number of genotypes $n$ is computed
 (using the $genotypeNum$ function). Each species $spec$ is
 allocated $m$ new live genotypes where:
 \begin{equation*}
m =  \frac{(genotypeNum\ genes\ spec)*\populationDefaultSize}{n}
 \end{equation*}
The equation above simply computes the number of genotypes to spawn for each species as a proportion of the
number of genotypes that can be spawned per species (in relation to the ecosytem's gene pool) in relation to the total number of genotypes
that must be spawned in order to obtain \populationDefaultSize{} genotypes in the whole ecosystem.


 \end{description}

\MySection{From Generation to Generation}
Below is an overview of the ABGP algorithm:
\begin{enumerate}
\item \label{beginAlg}
The user provides the input arguments, the context and the test cases.


\item \label{readInput}
The system deduces \GT{} from the test cases and builds the gene pool's kernel.

\item \label{init} The gene pool is grown randomly to size \maxComp{ } by randomly mutating the
     alleles that are already in it.  No new allele may be larger than
     \maxGeneComp.

\item \label{speciesSpawn1} The number of possible genotypes is
     calculated based on the species in the system and the type and number of
     genes in the gene pool. If it is possible to
     produce \populationDefaultSize{} genotypes, go to step \ref{eval}, otherwise
     go to step \ref{speciesSpawn2}

\item \label{speciesSpawn2} Produce new species either by modifying
     species already in the ecosystem or by brute search for
     new proofs of \GT{} with limited depth, using the types of the genes
     in the gene pool as propositions.
     Delete all the alleles in the gene pool that can not be used in
     any of the species in the ecosystem. Go to step \ref{init}.

\item \label{eval} \populationDefaultSize{} genotypes are assembled and evaluated on all test cases.
    The genotypes are scored based on the proportion of test cases their associated
    phenotypes  were able to correctly compute. If one a phenotype was able
     to compute all test cases, then the corresponding genotype is the solution, which is
     output as the result of the run which terminates successfully , otherwise, go
     to step \ref{iter}

\item \label{iter}
A negative selection (see \ref{selectionecosysstep}) operation which removes
genotypes, alleles and possibly whole species
from the ecosystem is applied. The ecosystem is then rebuilt to capacity,
go to step \ref{eval} and proceed to next generation.
 \end{enumerate}
\noindent
One of the features that distinguishes the \ABGPS{} from
other GP systems is that while evaluation is done at the phenotype
level, selection is applied at several level. In ABGP, genotypes are
used as statistical tools to evaluate the alleles that compose them
and the species upon which pattern they are built. As usual, the
fitness of a genotype is a proportionality of how close the
genotype's associated phenotype describes a solution, however, the
selection of genes and species is implicit as it piggybacks on the
selection process applied to genotypes.  In ABGP, the first
selection procedure occurs at the beginning of the creation of a new
generation. This section describes the procedure that creates a new
generation of genotypes from an existing generation containing
\populationDefaultSize{} evaluated genotypes. This is the iterative
step of the GP system and it is applied to a system that evolves an
ecosystem $\mathit{eco}$. The pseudo-code for this step is provided
in Program \ref{nextGen}.
\begin{Program}[h]
\begin{verbatim}
|pre condition 1: alive_eco eco =  \populationDefaultSize |
|pre condition 2: eco.generationCounter = n               |
-----------------------------------------------------------
next_generation eco =
\end{verbatim}
%\begin{comment}
%\begin{description}

%\end{description}
%\end{comment}
\begin{comment}
Step 1, see $selection\_filter$, program \ref{selFil}
\end{comment}
\begin{verbatim}
    selection_filter eco;
\end{verbatim}

\begin{comment}
Step 2, reconstruction of ecosystem, see section
\ref{newgenecreation89}
\end{comment}
\begin{verbatim}
    reconstruct_eco eco
-----------------------------------------------------------
| post condition: alive_eco eco =  \populationDefaultSize |
| post condition: eco.generationCounter = n + 1           |

\end{verbatim}
\caption{The $next\_generation$ function}\label{nextGen}
\end{Program}



\subsection{Filter Selection Step}\label{selectionecosysstep}
\noindent Program \ref{selFil} provides the selection procedure
pseudo-code. The first step in the production of a new generation
from an existing generation is to remove some genotypes from the
ecosystem. This step is inspired from the following two effects
observed in the biological world:
\begin{enumerate}
\item Birth is  one of the most dangerous time in the lifetime of an individual and  a newborn needs to possess at least a minimum level of fitness in order to reach childhood.
\item Some individuals do not reproduce. This is non-deterministically related to their fitness. In ABGP, this results in a round of selection that aims to remove some lower fitness genotype before they get a chance to pass their genes onto the next generation.
\item A species whose organisms have all died becomes extinct.
\item If all the organisms that carry a given gene in an ecosystem die before reproduction, that gene is removed from the gene pool.
\end{enumerate}

\begin{Program}[h]
\begin{verbatim}
| pre condition: alive_eco eco =  \populationDefaultSize                        |
-----------------------------------
selection_filter eco =
    selection_filter_genotypes eco;
    selection_filter_species eco;
    selection_filter_genes eco

-----------------------------------
| post condition: alive_eco eco <=  \populationDefaultSize - \reapPopulationSize |
| post condition: For all (species, population) pairs in eco.kingdom,            |
|    (alive_population population) > 0                                           |
| post condition: For all genes g in eco.genes, g.useInEcosystem > 0             |
\end{verbatim}
\caption{The $selection\_filter$ function}\label{selFil}
\end{Program}

\subsubsection{Filter Selection on Genotypes}\label{GenoSelection}
In ABGP, the initial selection filter step on genotype is composed of two sub-steps. Given an ecosystem $eco$, the
first sub-step is to non-deterministically kill all genotypes in $eco$ with fitness below a certain threshold.
``Killing" in this case means the change of status of the genotype from `Alive' to `Dead'.
%MODIFICATION_A corrected determinits error
This step is deterministic, so the threshold is quite low. After this has been done, the second
sub-step compares the number of genotypes marked as 'Alive', $(\mathit{alive\_eco}\ eco)$ to the value
$\text{\populationDefaultSize} - \text{\reapPopulationSize}$ (where \reapPopulationSize{} is a user supplied parameter
that fixes the strength of the selection pressure applied to the population). If the number of genotypes alive
is greater than this value, genotypes marked as 'Alive' are killed non-deterministically in proportion to their fitness values until:

\begin{equation*}
\mathit{alive\_eco}\ eco \leq  \populationDefaultSize - \reapPopulationSize
\end{equation*}


\subsubsection{Filter Selection on Species}\label{SpeciesSelection}
Similar to the filter selection step on genes (see \ref{GenesSelection} below), the filter selection step on species is simply a by-product of the selection step on genotypes. Following \ref{GenoSelection}, some species may no longer contain any genotypes marked as 'Alive'. These species are removed (and are referred to as {\em extinct}). A species that becomes extinct will no longer produce descendent species at the crossover process.  At the end of this sub-step, the following predicate holds on $eco$:
\begin{equation*}
\forall(species, population)\in eco.kingdom, (alive\_population\ population) > 0
\end{equation*}
\noindent
It is at the end of this step that a fitness value is assigned to the species that are still in the ecosystem. This species specific fitness value is computed as :
\begin{equation}
\frac{\text{sum of the fitness values of all genotypes marked as 'Alive' in $population$}}
{(alive\_population\ population)}
\end{equation}
where $population$ is the $Population$ object associated with the species. The fitness of the species is stored
in the $\mathit{fitness}$ field of $population$.


\subsubsection{Filter Selection on Genes}\label{GenesSelection}
Following \ref{GenoSelection}, some alleles may no longer be carried
by any genotypes. These are removed from the gene pool, eventually
making space for new alleles. At the end of this sub-step, all the
alleles in the gene pool are carried by at least one genotype, and
the following predicate holds:
\begin{equation*}
\forall\ g \in eco.genes, g.useInEcosystem > 0
\end{equation*}
\noindent
The number of genotypes that carry an allele $g$ is stored in $g$'s \field{useInEcosystem} field and
$g$'s \field{geneFitness} value can be computed as:

%MODIFICATION_A explaination for denominator
\begin{equation*}
\frac{\text{sum of the fitness values of all genotypes marked as 'Alive' in $eco$ that carry $g$}}{\field{g.useInEcosystem}}
\end{equation*}
\noindent
The denominator is necessary because what is calulated here is \emph{the average fitness of a particular allele}. To obtain this value, it is necessary
to sum the fitnesses of all the programs that carry the allele and to then divide by the number of such programs.

\subsection{Reconstruction of Ecosystem Step}\label{newgenecreation89}
The last step of the reconstruction process is the production of new
genotypes. This step is virtual, as no new live genotypes are
produced. Instead, some new unborn genotypes are produced. These may
already exist, or they may be constructed during the recombination
process. New alleles and new species may also be produced during the
recombination operations, resulting in further increase in the
number of 'Unborn' genotypes that live within the system. Once a sufficient
amount of unborn genotypes has been created, new genotypes are
marked as alive using the diversity optimizing method described in
section \ref{GenoSpawn}.
%New genotypes are spawned in
%proportion to the population's capacity...(alive + unborn /
%deafultsize) \noindent Step 2 of Program \ref{nextGen}(reproduced in
%listing \ref{Step2Prog}) is to rebuild the ecosystem to its desired
%\populationDefaultSize{} population default size.
\begin{Program}[h]
\begin{verbatim}
| pre condition: alive_eco eco <=  \populationDefaultSize - \reapPopulationSize |
| pre condition: For all (species, population) pairs in eco.kingdom,            |
|    (alive_population population) > 0                                          |
| pre condition: For all genes g in eco.genes, g.useInEcosystem > 0             |
-----------------------------------
let reconstruct_eco eco =
    let foundSolution = ref false in
    let sol = ref None in
    while (ecosystemIsNotFull( ) && not(foundSolution)) do
        match addNewLiveGenotypes eco with
            |None --> ( )
            |Some solution -->
            foundSolution := true;
            sol := Some solution
    done;
    eco.generationCounter <- eco.generationCounter + 1

-----------------------------------
| post condition: alive_eco eco =  \populationDefaultSize
\end{verbatim}
\caption{The $reconstruct\_eco$  function}\label{Step2Prog}
\end{Program}
\noindent The function simply calls the
$\mathit{addNewLiveGenotypes}$ function until the predicate
$\mathit{alive\_eco}\ eco =  \populationDefaultSize$ holds. The
pseudo-code for $\mathit{addNewLiveGenotypes}$ is given in Program
\ref{addNG}.
\begin{Program}[h]
{\small
\begin{verbatim}
| pre condition: alive_eco eco <=  \populationDefaultSize - \reapPopulationSize |
| pre condition: For all (species, population) pairs in eco.kingdom,            |
|    (alive_population population) > 0
| pre condition: For all genes g in eco.genes, g.useInEcosystem > 0             |
---------------------------------------------------------------------------------

 addNewLiveGenotypes eco  =
    let aliveNum = ref (liveGenotypes( )) in
    let doCrossover sol crossoverOp =
        match sol, liveGenotypes( ) with
            |Some _,_ --> sol
            |None, x when x  > !aliveNum --> None
            |_ --> crossoverOp eco in
    fold_left doCrossover None
    [simpleXover; geneMutationXover; speciesMutationXover]
--------------------------------------------------------------------------------
| post condition: alive_eco eco =  \populationDefaultSize                      |
\end{verbatim}}
\caption{The $addNewLiveGenotypes$ function}\label{addNG}
\end{Program}


\subsubsection{Producing New Genotypes}\label{xoverGeneral}
%\noindent
%\begin{Program}
%{\small
%\begin{verbatim}
%| pre condition: alive_eco eco <=  \populationDefaultSize - \reapPopulationSize|
%| pre condition: unborn_eco eco >= \reapPopulationSize                         |
%-------------------------------------------------------------------------------
%refill_ecosystem eco
%    do
%        Select two parent genotype a and b from the same
%        species in eco and produce a family of new genotypes
%        by creating a set of unborn genotypes G
%        such that for all g in G, the value:
%            gen_dist(a,g) + gen_dist(b,g) is minimum
%
%
%        Evaluate each new genotypes in G and mark them
%        as Alive
%    while (alive_eco eco <  \populationDefaultSize)
%--------------------------------------------------------
%|post condition: alive_eco eco =  \populationDefaultSize|
%\end{verbatim}}
%\caption{The $refill\_ecosystem$ function}\label{refEco}
%\end{Program}
\noindent
There are three crossover operations for \ABGP. Each
produces offspring at different genotypic distances from the parents
in the search space. The underlying principles of crossover scheme
for the system are:
\begin{itemize}
\item {\em Heredity}: offspring should be similar to their parents
\item {\em Variability}: offspring should not be identical to their parents
\end{itemize}
We applied these principles to both the structure (the species) and the composition (the genes) of
the genotype. In ABGP, crossover happens between two parents that belong to the same species.
The most simple case of crossover, mutation-free crossover is described below.

\subsubsection{Crossover Simple Case}
The next step is to apply simple crossover. Simple crossover is applied to two living genotypes that belong to the same species. It doesn't introduce any new genetic material in the
gene pool and doesn't create any new species.
\begin{figure}
\centering \epsfig{file=crossoverSimpleCase.eps, width=\linewidth}
\caption{The basic crossover case. Any of the 6 possible offspring belongs to the same species that both their parents belong to and each of the offspring genes originates from one or the other parent}\label{crossoverAAAA}
\end{figure}
\noindent
 Simple crossover is a basic recombination of
the genetic material of the two parents and the offspring produced are
somewhere in between both parents' positions in the search space. Each gene
carried by the offspring is carried by one of its parents in the same position.
An offspring only contains genetic material already carried by one or both of its parents,
with the added restriction that it may not be similar to any genotype that already exists in the
population (alive or dead). Figure \ref{crossoverAAAA} illustrates the simple case. In this
case, as the pattern on which the parent genotypes are constructed admits 3 slots for gene plugging,
there is a total of $2^3 - 2$ possible offspring that may be produced. In general, given two genotypes
belonging to the same species with $n$ slots for gene plugging, $2^{n-k} - 2$ offspring may be produced. $k$
is the number of slots in the parents genome that contain similar genes. In figure \ref{crossoverAAAA},
both genotypes belong to the species defined in the upper left portion of figure \ref{threegenotypesandspecies}.


\subsubsection{Crossover with Mutation I: Creation of New Genes}
Following this step, the value $(\mathit{alive\_eco}\ eco)$ may  still (and if it is isn't, eventually will as all the simple recombination possibilities are exhausted) be lower than $\populationDefaultSize - \reapPopulationSize$. If this is the case, crossover with mutation is applied. This step begins by rebuilding the pool to \maxComp{} using the genes that are in it as seed for new genes.  The fitness of a gene is calculated as the average of the fitness of the genotypes that carry it, and it is used to compute the probability function that will be used to select the genes that will undergo the mutation process that will form new genes.
\begin{figure}[h]
\centering \epsfig{file=crossoverMutationCase.eps, width=120mm}
\caption{Crossover with mutation generated by the introduction of a new gene in the gene pool. }\label{crossoverABBB}
\end{figure}
New gene are then used to generate new genotypes at crossover time by being inserted in appropriate position (as determined by its type) instead of a parent gene as in the simple case. Figure \ref{crossoverABBB} illustrates this subcase of crossover. While the crossover case with gene mutation represent a wider search space exploratory jump than the simple crossover case (a new simple gene might radically change the computational path taken by the program), it only produces offspring within the search space partition that is defined by the species to which the offspring's genotype belong. The next crossover scheme is more radical as it produces offspring outside the search space partition defined by the parent's species.


\subsubsection{Crossover with Mutation II: Creation of New Species}
The last mutation case is the one that creates a new species. As in nature, the first genotypes of a new species must be the offspring of genotypes that belong to a different species. In this crossover scenario, it is the species to which the two parent genotypes belong that is mutated. A new descendent species is produced from the ancestor species to which the genotypes belong. This is a macro mutation scenario and large structural modifications have a lower probability of producing high quality genotypes because they represent a wider jump in the search space than either simple crossover or crossover with gene mutation. In order to compensate,  when this crossover scheme is applied, all possible combinations deriving from the ancestor species are produced, sampling a wider subset of the search space partition defined by the species. Figure \ref{crossoverABBC} illustrates this crossover scenario. This crossover scheme is applied a maximum of two times in a given generation and only in one of the following situations:
\begin{itemize}
\item The two genotypes chosen for reproduction both belong to the highest 10th percentile of the population in terms of fitness.
\item All possible offspring (including those produced by gene mutation crossover) have already been evaluated for the two genotypes selected for reproduction.
\item There hasn't been a ``better than ever before" genotype produced in the last 3 generations (as a stagnation preventing measure)
\end{itemize}
\begin{figure}
\centering \epsfig{file=crossoverNewSpeciesCase.eps, width=150mm}
\caption{In this crossover scenario, a new species is created from the species to which both parent belong. The gene slots that match in the offspring species and in the parent species are filled as in the first case. The gene slots that do not match are filled from random choices in the gene pool}\label{crossoverABBC}
\end{figure}


%
%
%
%    \subsubsection{Re-Constructing the Gene Pool}
%    Once the evaluation procedure has been completed, some genotypes may have obtained a $0$ fitness score of. In particular, this may be caused by a gene that has the effect of producing a run time error, in whcih case, all the genotypes that carry this gene will have nil fitness scores. These genes are themeselves seldcted agaisnt as they wopikld be in a rela biological systemAfter negative selection as been aplied to the population, genotypes are removed. there usually will remain some gene in the gene pool athta are  generation, genes that are not carried by any genotypes are removed. In particular, a gene , will have no genotype The gene pool is re-built (up to \maxComp) at the beginning of each iteration of the system. The genes that are still in the pool after the last generation's selection process are randomly
%    mutated to construct new genes. The
%    construction process stops when
%    the sum of the complexities of all objects in the pool is greater than \maxComp{},
%    one of the system-wide variables defined for the system.
%    The rules used to produce new terms and new types are based on logic derivation rules. Each rule is
%    a meta-operation that takes an \tok{} as input and
%    outputs another \tok. For example, assuming the context of table \ref{tab:ctxex1}, we may have an
%    rule that starts with the input type $\typ{\Pi X.\AT{X}{\AT{X}{X}}}$, randomly
%    picks a type \Type{} from the keys of \BP{} and produces the type
%    $\AT{\Type}{\AT{\Type}{\Type}}$. Another rule might start with the term
%    $t^{\AT{\Type}{\Type}}$, picks a term $a^{\Type}$ in \BPset{} and
%    produces the term $(t\ a)$.
%
%
%    \subsection{Specifying a Problem}
%
%
%   % \hline
%%    Test cases\\
%    \begin{table}
%    \begin{center}
%    \begin{tabular}{|l|}
%    \hline
%    test cases\\
%    \hline
%    $false,false,false$\\
%    $false,true,true$\\
%    $true,false,true$\\
%    $true,true,false$\\
%    \hline
%
%    \end{tabular}
%    \caption{...}\label{tab:tests}
%    \end{center}
%    \end{table}
%
%    \noindent
%    A problem may be specified by:
%    \begin{enumerate}
%    \item {\em Test Cases}: Each test case is a comma separated list of arguments followed by the result that the function that is to be evolved should produce. For example, the evolution of an $xor$ function is specified by the test cases listed in table \ref{tab:tests} and (in this case) the system needs to know what $true$ and $false$ means. This meaning is provided in the context.
%Note that in this case, we could achieve the same results without
%specifying a context by using the pure \SF{} syntax to describe the
%test cases. For this example, the context is nothing more than a
%tool to facilitate the understanding of the solution programs.
%    \item {\em Goal Type}: {\em \GT{ }} is the type of the solution program. If the system is
%to evolve an $xor$ function, as in table \ref{tab:tcs}, \GT{ } is
%$\AT{Boolean}{\AT{Boolean}{Boolean}}$. If the system should evolve a
%function that takes a list of strings as argument and returns the
%string resulting from the concatenation of the elements of the list,
%then \GT{ } is $\AT{(\Pi
%X.\AT{X}{\AT{(\AT{String}{\AT{X}{X}})}{X}})}{String}$.\subsection{Initializing a Run}

\MySection{Conclusion}
In this chapter, we presented the ABGP system. We've built an implementation of this
system and in the next chapter, we  describe the results that we've been able to
obtain with it.
